package com.example.hot100;

import com.example.linked.ListNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
 *
 *  示例 1：
 * 输入：head = [1,2,2,1]
 * 输出：true
 *
 *  示例 2：
 * 输入：head = [1,2]
 * 输出：false
 */
public class Leetcode234_IsPalindrome {
    public static void main(String[] args) {
        ListNode root = new ListNode(1);
        root.next = new ListNode(2);
        root.next.next = new ListNode(2);
        root.next.next.next = new ListNode(1);
        System.out.println(new Solution().isPalindrome(root));
    }

    static class Solution {
        /**
         * 先找到链表的中间节点(快慢指针)，
         * 然后将后半段进行反转然后判断两部分是否每个节点都一样(链表翻转)
         * @param head
         * @return
         */
        private boolean isPalindrome2(ListNode head) {
            ListNode midNode = getMidNode(head);
            ListNode reverted = revert(midNode);
            ListNode tmp1 = head, tmp2 = reverted;
            while (tmp1 != null && tmp2 != null) {
                if (tmp1.val != tmp2.val) return false;
                tmp1 = tmp1.next;
                tmp2 = tmp2.next;
            }
            return true;
        }

        private ListNode revert(ListNode root) {
            ListNode pre = null, cur = root, tmp = root;
            while (cur != null) {
                tmp = tmp.next;
                cur.next = pre;
                pre = cur;
                cur = tmp;
            }
            return pre;
        }

        private ListNode getMidNode(ListNode head) {
            ListNode slow = head, fast = head;
            while (fast.next != null && fast.next.next != null) {
                fast = fast.next.next;
                slow = slow.next;
            }
            return slow.next;
        }

        /**
         * 暴力解法
         * 先遍历链表得到序列，然后判断
         * @param head
         * @return
         */
        private boolean isPalindrome1(ListNode head) {
            if (head == null) return true;
            ListNode tmp = head;
            List<Integer> list = new ArrayList<>();
            while (tmp != null) {
                list.add(tmp.val);
                tmp = tmp.next;
            }
            int start = 0, end = list.size() - 1;
            while (start < end) {
                if (list.get(start++) != list.get(end--)) return false;
            }
            return true;
        }

        public boolean isPalindrome(ListNode head) {
            return isPalindrome2(head);
        }
    }
}
